/*
** Tree's ElemrntType is different from Stack's / Queue's!
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXSIZE 100
#define NoInfo 0

typedef struct TNode* Position;
typedef Position BinTree;
typedef BinTree ElementType;
struct TNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

typedef struct SNode* PtrToSNode;
struct SNode {
    ElementType* Data;
    int Top;
    int Maxsize;
};
typedef PtrToSNode Stack;
Stack CreateStack ( int Maxsize ) {
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType*)malloc(Maxsize*sizeof(ElementType));
    S->Top = -1;
    S->Maxsize = Maxsize;
    return S;
}
bool StackEmpty ( Stack S ) {
    return  (S->Top == -1);
}
ElementType Pop ( Stack S ) {
    if ( StackEmpty(S) ) {
        printf("Stack Empty\n");
        exit(-9);
    }
    return ( S->Data[(S->Top)--] );
}
bool StackFull ( Stack S ) {
    return ( S->Top == (S->Maxsize-1) );
}
void Push ( Stack S, ElementType X ) {
    if ( StackFull(S) ) {
        printf("Stack Full\n");
        exit(-10);
    }
    S->Data[++(S->Top)] = X;
}

typedef struct QNode* PtrToQNode;
struct QNode {
    ElementType* Data;
    int Front, Rear;
    int Maxsize;
};
typedef PtrToQNode Queue;
Queue CreateQueue ( int Maxsize ) {
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType*)malloc(sizeof(Maxsize*sizeof(struct QNode)));
    Q->Front = Q->Rear = 0;
    Q->Maxsize = Maxsize;
    return Q;
}
bool QueueEmpty ( Queue Q ) {
    return ( Q->Front == Q->Rear );
}
ElementType DeleteQ ( Queue Q ) {
    if ( QueueEmpty(Q) ) {
        printf("Queue Empty\n");
        exit(-11);
    }
    Q->Front = ( Q->Front + 1 ) % ( Q->Maxsize );
    return ( Q->Data[ Q->Front ] );
}
bool QueueFull ( Queue Q ) {
    return ( ( (Q->Rear) + 1 ) % ( Q->Maxsize ) == ( Q->Front ) );
}
void AddQ ( Queue Q, ElementType X ) {
    if ( QueueFull(Q) ) {
        printf("Queue Full\n");
        exit(-12);
    }
    Q->Rear = ( Q->Rear + 1 ) % ( Q->Maxsize );
    Q->Data[Q->Rear] = X;
}

bool IsEmpty ( BinTree BT );

// void Traversal ( BinTree BT );
void InorderTraversal ( BinTree BT );
void PreorderTraversal ( BinTree BT );
void PostorderTraversal ( BinTree BT );
void InorderTraversal1 ( BinTree BT );
void LevelorderTraversal ( BinTree BT );
void PreorderPrintLeaves ( BinTree BT );
int GetHeight ( BinTree BT );
BinTree CreatBinTree ();

int main () {
    return 0;
}

bool IsEmpty ( BinTree BT );

void InorderTraversal ( BinTree BT ) {
    if (BT) {
        InorderTraversal(BT->Left);
        printf("%d",BT->Data);
        InorderTraversal(BT->Right);
    }
}
void PreorderTraversal ( BinTree BT ) {
    if (BT) {
        printf("%d",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
void PostorderTraversal ( BinTree BT ) {
    if (BT) {
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf("%d",BT->Data);
    }
}
void InorderTraversal1 ( BinTree BT ) {
    BinTree T;
    Stack S = CreateStack(MAXSIZE);
    T = BT;
    while ( T || !StackEmpty(S) ) {
        while (T) {
            Push(S,T);
            T = T->Left;
        }
        T = Pop(S);
        printf("%d",T->Data);
        T = T->Right;
    }
}
void LevelorderTraversal ( BinTree BT ) {
    Queue Q;
    BinTree T;
    if (!BT) return;
    Q = CreateQueue(MAXSIZE);
    AddQ(Q,BT);
    while ( !QueueEmpty(Q) ) {
        T = DeleteQ(Q);
        printf("%d",T->Data);
        if ( T->Left )  AddQ(Q,T->Left);
        if ( T->Right ) AddQ(Q,T->Right);
    }
}

void PreorderPrintLeaves ( BinTree BT ) {
    if (BT) {
        if ( !BT->Left && !BT->Right ) printf("%d",BT->Data);
        PreorderPrintLeaves(BT->Left);
        PreorderPrintLeaves(BT->Right);
    }
}

int GetHeight ( BinTree BT ) {
    int HL, HR, MaxH;
    if (BT) {
        HL = GetHeight(BT->Left);
        HR = GetHeight(BT->Right);
        MaxH = HL > HR ? HL : HR;
        return ( MaxH + 1 );
    }
    else return 0;
}

BinTree CreatBinTree () {
    ElementType Data;
    
    BinTree BT, T;
    Queue Q = CreateQueue(MAXSIZE);

    scanf("%d",&Data);
    if ( Data == NoInfo ) return NULL;
        
    BT = (BinTree)malloc(sizeof(struct TNode));
    BT->Data = Data;
    BT->Left = BT->Right = NULL;
    AddQ(Q,BT);

    while ( !QueueEmpty(Q) ) {
        T = DeleteQ(Q);
        scanf("%d",&Data);
        if ( Data == NoInfo ) T->Left = NULL;
        else {
            T->Left = (BinTree)malloc(sizeof( struct TNode ));
            T->Left->Data = Data;
            T->Left->Left = T->Left->Right = NULL;
            AddQ(Q,T->Left);
        }
        scanf("%d",&Data);
        if ( Data == NoInfo ) T->Right = NULL;
        else {
            T->Right = (BinTree)malloc(sizeof(struct TNode));
            T->Right->Data = Data;
            T->Right->Left = T->Right->Right = NULL;
            AddQ(Q,T->Right);
        }
    }
    return BT;
} 